package leetcode.tree.binary.traversal;

import leetcode.tree.binary.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 105. 使用前序与中序遍历序列构造二叉树
 *
 */
public class BuildTree {

    public static void main(String[] args) {
        BuildTree solution = new BuildTree();
        // 先序遍历数组
//        int[] preorder = {1, 2, 4, 5, 3, 6, 7};
//        // 中序遍历数组
//        int[] inorder = {4, 2, 5, 1, 6, 3, 7};

        int[] preorder = {1, 2};
        int[] inorder = {2, 1};
        TreeNode tree = solution.buildTree(preorder, inorder);
        System.out.println(tree);
    }


    /**
     * 递归实现 自己写的
     *
     * @param preorder  前序遍历数组
     * @param inorder   中序遍历数组
     * @return
     */
    public TreeNode buildTree0(int[] preorder, int[] inorder) {
        return build(preorder, 0, preorder.length - 1,
                inorder, 0, inorder.length - 1);
    }

    /**
     *
     * @param preorder      前序遍历数组
     * @param start1        前序遍历数组对应的起始位置
     * @param end1          前序遍历数组对应的结束位置
     * @param inorder       中序遍历数组
     * @param start2        中序遍历数组起始位置
     * @param end2          中序遍历数组结束位置
     * @return
     */
    public TreeNode build(int[] preorder, int start1, int end1, int[] inorder, int start2, int end2) {
        // 前序遍历数组的第一个元素就是根节点
        int rootValue = preorder[start1];
        TreeNode root = new TreeNode(rootValue);

        // 只剩一个元素了 就是叶子节点
        if (start1 >= end1) {
            return root;
        }

        // 找出中序遍历的根节点位置
        int mid = start2;
        for (int i = start2; i <= end2; i++) {
            if (inorder[i] == rootValue) {
                mid = i;
                break;
            }
        }

        // 左子树长度
        int leftLen = mid - start2;
        // 右子树长度
        int rightLen = end2 - mid;

        // 左子树递归
        if (leftLen > 0) {
            root.left = build(preorder, start1 + 1, start1 + leftLen, inorder, start2, mid - 1);
        }

        // 右子树递归
        if (rightLen > 0) {
            root.right = build(preorder, start1 + leftLen + 1, end1, inorder, mid + 1, end2);
        }
        return root;
    }


    /**
     * 递归实现 官方写法
     *
     * 一开始使用 Map存储中序遍历数组中每个元素与其下标的对应位置
     *
     * @param preorder 前序遍历数组
     * @param inorder  中序遍历数组
     * @return 树
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    private Map<Integer, Integer> indexMap;

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return null;
        }

        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);

        // 先把根节点建立出来
        TreeNode root = new TreeNode(preorder[preorder_root]);

        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;

        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);

        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

}
